A central question in knowledge representation is the following: given some knowledge representation formalism, is it possible, and if so how, to simplify parts of a knowledge base without affecting its meaning, even in the light of additional information? The term strong equivalence was coined in the literature, i.e. strongly equivalent knowledge bases can be locally replaced by each other in a bigger theory without changing the semantics of the latter. In contrast to classical (monotone) logics where standard and strong equivalence coincide, it is possible to find ordinary but not strongly equivalent objects for any nonmonotonic formalism available in the literature.

Given the large variety of existing logical formalisms it is of utmost importance to select the most adequate one for a specific purpose, e.g. for representing the knowledge relevant for a particular application or for using the formalism as a modeling tool for problem solving. Awareness of the nature of a logical formalism, in other words, of its fundamental intrinsic properties, is indispensable and provides the basis of an informed choice. One such intrinsic property of logic-based knowledge representation languages is the context-dependency of pieces of knowledge. In classical propositional logic, for example, there is no such context-dependence: whenever two sets of formulas are equivalent in the sense of having the same models (ordinary equivalence), then they are mutually replaceable in arbitrary contexts (strong equivalence). However, a large number of commonly used formalisms are not like classical logic which leads to a series of interesting developments.

A central question in knowledge representation is the following: given some knowledge representation formalism, is it possible, and if so how, to simplify parts of a knowledge base without affecting its meaning, even in the light of additional information? The term strong equivalence was coined in the literature, i.e. strongly equivalent knowledge bases can be locally replaced by each other in a bigger theory without changing the semantics of the latter. In contrast to classical (monotone) logics where standard and strong equivalence coincide, it is possible to find ordinary but not strongly equivalent objects for any nonmonotonic formalism available in the literature. This paper addresses these questions in the context of abstract argumentation theory. Much effort has been spent to characterize several argumentation tailored equivalence notions w.r.t. extension-based semantics. In recent times labelling-based semantics have received increasing attention, for example in connection with algorithms computing extensions, proof procedures, dialogue games, dynamics in argumentation as well as belief revision in general. Of course, equivalence notions allowing for replacements are of high interest for the mentioned topics. In this paper we provide kernel-based characterization theorems for semantics based on complete labellings as well as admissible labellings w.r.t. eight different equivalence notions including the aforementioned most prominent one, namely strong equivalence.

We explore equivalence relations between states in Markov Decision Processes and Partially Observable Markov Decision Processes. We focus on two different equivalence notions: bisimulation (Givan et al., 2003) and a notion of trace equivalence, under which states are considered equivalent if they generate the same conditional probability distributions over observation sequences (where the conditioning is on action sequences).  We show that the relationship between these two equivalence notions changes depending on the amount and nature of the partial observability. We also present an alternate characterization of bisimulation based on trajectory equivalence.

Logic programming under the answer-set semantics nowadays deals with numerous different notions of program equivalence. This is due to the fact that equivalence for substitution (known as strong equivalence) and ordinary equivalence are different concepts. The former holds, given programs P and Q, iff P can be faithfully replaced by Q within any context R, while the latter holds iff P and Q provide the same output, that is, they have the same answer sets. Notions in between strong and ordinary equivalence have been introduced as theoretical tools to compare incomplete programs and are defined by either restricting the syntactic structure of the considered context programs R or by bounding the set A of atoms allowed to occur in R (relativized equivalence).For the latter approach, different A yield properly different equivalence notions, in general. For the former approach, however, it turned out that any ``reasonable'' syntactic restriction to R coincides with either ordinary, strong, or uniform equivalence. In this paper, we propose a parameterization for equivalence notions which takes care of both such kinds of restrictions simultaneously by bounding, on the one hand, the atoms which are allowed to occur in the rule heads of the context and, on the other hand, the atoms which are allowed to occur in the rule bodies of the context. We introduce a general semantical characterization which includes known ones as SE-models (for strong equivalence) or UE-models (for uniform equivalence) as special cases. Moreover,we provide complexity bounds for the problem in question and sketch a possible implementation method. To appear in Theory and Practice of Logic Programming (TPLP).